package com.shm.leetcode;

import java.util.PriorityQueue;

/**
 * 407. 接雨水 II
 * 给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
 *
 *
 *
 * 示例 1:
 *
 *
 *
 * 输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
 * 输出: 4
 * 解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。
 * 示例 2:
 *
 *
 *
 * 输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
 * 输出: 10
 *
 *
 * 提示:
 *
 * m == heightMap.length
 * n == heightMap[i].length
 * 1 <= m, n <= 200
 * 0 <= heightMap[i][j] <= 2 * 104
 * @author SHM
 */
public class TrapRainWater {
    /**
     * 方法一：最小堆
     * 思路与算法
     *
     * 本题为经典题目，解题的原理和方法都可以参考「42.接雨水」，本题主要从一维数组变成了二维数组。
     * 首先我们思考一下什么样的方块一定可以接住水：
     *
     * 该方块不为最外层的方块；
     * 该方块自身的高度比其上下左右四个相邻的方块接水后的高度都要低；
     * 我们假设方块的索引为 (i,j)(i,j)，方块的高度为 \textit{heightMap}[i][j]heightMap[i][j]，方块接水后的高度为 \textit{water}[i][j]water[i][j]。则我们知道方块 (i,j)(i,j) 的接水后的高度为：
     *
     * \textit{water}[i][j] = \max(\textit{heightMap}[i],\min(\textit{water}[i-1][j],\textit{water}[i+1][j],\textit{water}[i][j-1],\textit{water}[i][j+1]))
     * water[i][j]=max(heightMap[i][j],min(water[i−1][j],water[i+1][j],water[i][j−1],water[i][j+1]))
     *
     * 我们知道方块 (i,j)(i,j) 实际接水的容量计算公式为 \textit{water}[i][j] - \textit{heightMap}[i][j]water[i][j]−heightMap[i][j]。
     * 首先我们可以确定的是，矩阵的最外层的方块接水后的高度就是方块的自身高度，因为最外层的方块无法接水，因此最外层的方块 \textit{water}[i][j] = \textit{heightMap}[i][j]water[i][j]=heightMap[i][j]。
     *
     * 根据木桶原理，接到的雨水的高度由这个容器周围最短的木板来确定的。我们可以知道容器内水的高度取决于最外层高度最低的方块，如图 11 所示：
     *
     *
     *
     * 我们假设已经知道最外层的方块接水后的高度的最小值，则此时我们根据木桶原理，肯定可以确定最小高度方块的相邻方块的接水高度。我们同时更新最外层的方块标记，我们在新的最外层的方块再次找到接水后的高度的最小值，同时确定与其相邻的方块的接水高度，如图 22 所示:
     *
     *
     *
     * 然后再次更新最外层，依次迭代直到求出所有的方块的接水高度，即可知道矩阵中的接水容量。
     * 复杂度分析
     *
     * 时间复杂度：O(MN\log(M+N))O(MNlog(M+N))，其中 MM 是矩阵的行数，NN 是矩阵的列数。我们需要将矩阵中的每个元素都进行遍历，同时将每个元素都需要插入到优先队列中，总共需要向队列中插入 MNMN 个元素，每次堆进行调整的时间复杂度为 O(\log(M+N))O(log(M+N))，因此总的时间复杂度为 O(MN\log(M+N))O(MNlog(M+N))。
     *
     * 空间复杂度：O(MN)O(MN)，其中 MM 是矩阵的行数，NN 是矩阵的列数。我们需要创建额外的空间对元素进行标记，优先队列中最多存储 O(MN)O(MN) 个元素，因此空间复杂度度为 O(MN)O(MN)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/trapping-rain-water-ii/solution/jie-yu-shui-ii-by-leetcode-solution-vlj3/
     *
     * @param heightMap
     * @return
     */
    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length;
        int n = heightMap[0].length;
        if (m<=2||n<=2){
            return 0;
        }
        boolean[][] visit = new boolean[m][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->(o1[1]-o2[1]));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i==0 || i==m-1 || j==0 || j==n-1){
                    pq.offer(new int[]{i*n+j,heightMap[i][j]});
                    visit[i][j] = true;
                }
            }
        }
        int res = 0;
        int[][] direct = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
        while (!pq.isEmpty()){
            int[] curr = pq.poll();
            for (int i = 0; i < 4; i++) {
                int nx = curr[0]/n+direct[i][0];
                int ny = curr[0]%n+direct[i][1];
                if (nx>=0&&nx<m&&ny>=0&&ny<n&&!visit[nx][ny]){
                    if (curr[1]>heightMap[nx][ny]){
                        res+=curr[1]-heightMap[nx][ny];
                    }
                    pq.offer(new int[]{nx*n+ny,Math.max(heightMap[nx][ny],curr[1])});
                    visit[nx][ny]=true;
                }
            }
        }
        return res;
    }
}
